export class SortedMapByValue<K, V> {
    private keyToValue: Map<K, V> = new Map(); // 键到值的映射
    private valueToKeys: Map<V, Set<K>> = new Map(); // 值到键集合的映射
    private sortedValues: V[] = []; // 排序后的值数组
    private valueToRank: Map<V, number> = new Map(); // 值到排名的映射

    constructor(
        private comparator: (a: V, b: V) => number = (a: any, b: any) => {
            if (a < b) return -1;
            if (a > b) return 1;
            return 0;
        }
    ) {}

    /**
     * 设置键值对
     */
    set(key: K, value: V): void {
        // 如果键已存在，先删除旧值
        if (this.keyToValue.has(key)) {
            const oldValue = this.keyToValue.get(key)!;
            this.removeKeyFromValue(oldValue, key);

            // 如果该值没有其他键引用，从排序数组中移除
            if (!this.valueToKeys.has(oldValue) || this.valueToKeys.get(oldValue)!.size === 0) {
                this.removeValueFromSortedArray(oldValue);
            }
        }

        // 设置新值
        this.keyToValue.set(key, value);

        // 更新值到键的映射
        if (!this.valueToKeys.has(value)) {
            this.valueToKeys.set(value, new Set());
        }
        this.valueToKeys.get(value)!.add(key);

        // 如果值不存在于排序数组中，添加并排序
        if (!this.valueToRank.has(value)) {
            this.insertValueIntoSortedArray(value);
        }
    }

    /**
     * 获取键对应的值
     */
    get(key: K): V | undefined {
        return this.keyToValue.get(key);
    }

    /**
     * 删除键值对
     */
    delete(key: K): boolean {
        if (!this.keyToValue.has(key)) {
            return false;
        }

        const value = this.keyToValue.get(key)!;
        this.keyToValue.delete(key);
        this.removeKeyFromValue(value, key);

        // 如果该值没有其他键引用，从排序数组中移除
        if (!this.valueToKeys.has(value) || this.valueToKeys.get(value)!.size === 0) {
            this.removeValueFromSortedArray(value);
        }

        return true;
    }

    /**
     * 检查是否包含键
     */
    has(key: K): boolean {
        return this.keyToValue.has(key);
    }

    /**
     * 获取值对应的排名（从小到大，从0开始），O(1) 复杂度
     */
    getRankByValue(value: V): number {
        return this.valueToRank.get(value) ?? -1;
    }

    /**
     * 获取键对应的值的排名
     */
    getRankByKey(key: K): number {
        const value = this.keyToValue.get(key);
        return value !== undefined ? this.getRankByValue(value) : -1;
    }

    /**
     * 根据排名获取值
     */
    getValueByRank(rank: number): V | undefined {
        return this.sortedValues[rank];
    }

    /**
     * 根据排名获取键集合
     */
    getKeysByRank(rank: number): Set<K> | undefined {
        const value = this.sortedValues[rank];
        return value !== undefined ? this.valueToKeys.get(value) : undefined;
    }

    /**
     * 获取最小值
     */
    get minValue(): V | undefined {
        return this.sortedValues[0];
    }

    /**
     * 获取最大值
     */
    get maxValue(): V | undefined {
        return this.sortedValues[this.sortedValues.length - 1];
    }

    /**
     * 获取最小值的键集合
     */
    get minKeys(): Set<K> | undefined {
        const minValue = this.minValue;
        return minValue !== undefined ? this.valueToKeys.get(minValue) : undefined;
    }

    /**
     * 获取最大值的键集合
     */
    get maxKeys(): Set<K> | undefined {
        const maxValue = this.maxValue;
        return maxValue !== undefined ? this.valueToKeys.get(maxValue) : undefined;
    }

    /**
     * 获取所有键
     */
    get keys(): IterableIterator<K> {
        return this.keyToValue.keys();
    }

    /**
     * 获取所有值（按排序顺序）
     */
    get values(): V[] {
        return [...this.sortedValues];
    }

    /**
     * 获取所有键值对（按值排序）
     */
    get entries(): Array<[K, V]> {
        const result: Array<[K, V]> = [];

        for (const value of this.sortedValues) {
            const keys = this.valueToKeys.get(value);
            if (keys) {
                for (const key of keys) {
                    result.push([key, value]);
                }
            }
        }

        return result;
    }

    /**
     * 获取大小
     */
    get size(): number {
        return this.keyToValue.size;
    }

    /**
     * 清空
     */
    clear(): void {
        this.keyToValue.clear();
        this.valueToKeys.clear();
        this.sortedValues = [];
        this.valueToRank.clear();
    }

    /**
     * 遍历（按值排序）
     */
    forEach(callback: (value: V, key: K, map: SortedMapByValue<K, V>) => void): void {
        for (const [key, value] of this.entries) {
            callback(value, key, this);
        }
    }

    /**
     * 从值中移除键
     */
    private removeKeyFromValue(value: V, key: K): void {
        const keys = this.valueToKeys.get(value);
        if (keys) {
            keys.delete(key);
            if (keys.size === 0) {
                this.valueToKeys.delete(value);
            }
        }
    }

    /**
     * 从排序数组中移除值
     */
    private removeValueFromSortedArray(value: V): void {
        const rank = this.valueToRank.get(value);
        if (rank !== undefined) {
            this.sortedValues.splice(rank, 1);
            this.valueToRank.delete(value);
            this.updateRanksFrom(rank);
        }
    }

    /**
     * 将值插入排序数组
     */
    private insertValueIntoSortedArray(value: V): void {
        // 使用二分查找找到插入位置
        let left = 0;
        let right = this.sortedValues.length - 1;
        let insertIndex = this.sortedValues.length;

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            const comparison = this.comparator(value, this.sortedValues[mid]);

            if (comparison < 0) {
                insertIndex = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // 插入值
        this.sortedValues.splice(insertIndex, 0, value);

        // 更新排名映射
        this.updateRanksFrom(insertIndex);
    }

    /**
     * 从指定位置开始更新排名
     */
    private updateRanksFrom(startIndex: number): void {
        for (let i = startIndex; i < this.sortedValues.length; i++) {
            this.valueToRank.set(this.sortedValues[i], i);
        }
    }
}